In Wideband-code Division Multiple Access (W-CDMA) systems and Long Term Evolution (LTE) systems that have been standardized in the 3rd Generation Partnership Project (3GPP) in recent years, turbo codes are used as error correcting codes. In error correction that involves use of turbo codes, a Log Likelihood Ratio (hereinafter may also be referred to as an “LLR”) for each bit is calculated, from a received symbol, as soft decision information. Iterative decoding using the obtained soft decision information makes it possible to achieve performance that is close to the Shannon limit.
An LLR for each bit is a logarithm of a ratio of likelihood that a bit value of the bit is “0” to likelihood that it is “1”. A log likelihood ratio LLRi for the i-th bit (i is an integer greater than or equal to 1) in a received symbol r may be expressed by equation (1) below:
                                                                        LLR                i                            =                            ⁢                              log                ⁢                                  {                                                                                    ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                0                                                            )                                                                                                                          ⁢                                                                                          ⁢                                              P                        ⁡                                                  (                                                      s                            ⁢                                                          |                                                        ⁢                            r                                                    )                                                                                                                                    ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                1                                                            )                                                                                                                          ⁢                                                                                          ⁢                                              P                        ⁡                                                  (                                                      s                            ⁢                                                          |                                                        ⁢                            r                                                    )                                                                                                      }                                                                                                        =                            ⁢                              log                ⁢                                  {                                                                                    ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                0                                                            )                                                                                                                          ⁢                                                                                          ⁢                                                                        P                          ⁡                                                      (                                                          r                              ⁢                                                              |                                                            ⁢                              s                                                        )                                                                          ⁢                                                  P                          ⁡                                                      (                            s                            )                                                                                                                                                              ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                1                                                            )                                                                                                                          ⁢                                                                                          ⁢                                                                        P                          ⁡                                                      (                                                          r                              ⁢                                                              |                                                            ⁢                              s                                                        )                                                                          ⁢                                                  P                          ⁡                                                      (                            s                            )                                                                                                                                }                                                                                                        =                            ⁢                              log                ⁢                                  {                                                                                    ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                0                                                            )                                                                                                                          ⁢                                                                                          ⁢                                              P                        ⁡                                                  (                                                      r                            ⁢                                                          |                                                        ⁢                            s                                                    )                                                                                                                                    ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                1                                                            )                                                                                                                          ⁢                                                                                          ⁢                                              P                        ⁡                                                  (                                                      r                            ⁢                                                          |                                                        ⁢                            s                                                    )                                                                                                      }                                                                                                        =                            ⁢                                                log                  ⁢                                      {                                                                  ∑                                                  s                          ∈                                                      s                            ⁡                                                          (                                                                                                b                                  i                                                                =                                0                                                            )                                                                                                                          ⁢                                                                                          ⁢                                                                        1                                                                                    2                              ⁢                                                              πσ                                2                                                                                                                                    ⁢                        exp                        ⁢                                                  {                                                      -                                                                                                                            (                                                                      r                                    -                                    s                                                                    )                                                                2                                                                                            2                                ⁢                                                                  σ                                  2                                                                                                                                              }                                                                                      }                                                  -                                                                                                      ⁢                              log                ⁢                                  {                                                            ∑                                              s                        ∈                                                  s                          ⁡                                                      (                                                                                          b                                i                                                            =                              1                                                        )                                                                                                                ⁢                                                                                  ⁢                                                                  1                                                                              2                            ⁢                                                          πσ                              2                                                                                                                          ⁢                      exp                      ⁢                                              {                                                  -                                                                                                                    (                                                                  r                                  -                                  s                                                                )                                                            2                                                                                      2                              ⁢                                                              σ                                2                                                                                                                                    }                                                                              }                                                                                                        =                            ⁢                                                                    min                                          s                      ∈                                              s                        ⁡                                                  (                                                                                    b                              i                                                        =                            0                                                    )                                                                                                      ⁢                                      [                                          -                                                                                                    (                                                          r                              -                              s                                                        )                                                    2                                                                          2                          ⁢                                                      σ                            2                                                                                                                ]                                                  -                                                      min                                          s                      ∈                                              s                        ⁡                                                  (                                                                                    b                              i                                                        =                            1                                                    )                                                                                                      ⁢                                      [                                          -                                                                                                    (                                                          r                              -                              s                                                        )                                                    2                                                                          2                          ⁢                                                      σ                            2                                                                                                                ]                                                                                                                          =                            ⁢                                                -                                      1                                          2                      ⁢                                              σ                        2                                                                                            ⁢                                  (                                                            d                                              0                        ,                                                                                                  ⁢                        min                                            2                                        -                                          d                                              1                        ,                        min                                            2                                                        )                                                                                        (        1        )            
Equation (1) uses the Bayes' theorem, assumes that occurrence probabilities of all transmitted symbols are the same, and is transformed using the relationship of the following equation (2). In other words, the log likelihood ratio LLRi is expressed using variance σ and minimum distances d0,min and d1,min between constellation points in an IQ plane:
                              log          (                                    ∑              i                        ⁢                                                  ⁢                          exp              ⁡                              (                                  -                                      x                    i                                                  )                                              )                ≈                  -                      min            ⁡                          (                              x                i                            )                                                          (        2        )            
As may be seen from equation (1), the log likelihood ratio LLRi is expressed using the minimum distance d0,min between the received symbol r and a constellation point corresponding to a bit having a bit value of “0”, and the minimum distance d1,min between the received symbol r and a constellation point corresponding to a bit having a bit value of “1” in the IQ plane. Specifically, for example, when quadrature phase shift keying (QPSK) is used as a modulation scheme, two-bit sets “00”, “01”, “10”, and “11” are assigned to four points (K, K), (K, −K), (−K, K), and (−K, −K) in the IQ plane, respectively, where K is a reference amplitude value obtained from a coefficient depending on the modulation scheme and a channel estimate. A description will be given of an LLR for the first bit when the received symbol r are at the position marked with a star in FIG. 19.
Constellation points whose first bits have a bit value of “0” are (K, K) and (K, −K) corresponding to “00” and “01”, respectively. A constellation point closest to the received symbol r is (K, K) corresponding to “00”. Therefore, the minimum distance d0,min is the Euclidean distance between the received symbol r and (K, K). Similarly, the minimum distance d1,min between a constellation point whose first bit has a bit value of “1” and the received symbol r is the Euclidean distance between the received symbol r and (−K, K). Thus, the LLR for the first bit of the received symbol r may be determined from the minimum distances d0,min and d1,min illustrated in FIG. 19.
As may be seen from FIG. 19, each bit is independently mapped to an in-phase component (hereinafter referred to as an “I component”) or to a quadrature component (hereinafter referred to as a “Q component”) so that the first bit is mapped to the I component and the second bit is mapped to the Q component. Therefore, for each bit, the attention may be focused on the I or Q component of the received symbol r to determine the LLR from the minimum distance in a one-dimensional space. That is, when the I component of the received symbol r is a real part Re(r) and the Q component of the received symbol r is an imaginary part Im(r), LLRs for the first and second bits may be expressed by equations (3) below:
                    {                                                                              LLR                  1                                =                                  -                                                            1                                              2                        ⁢                                                  σ                          2                                                                                      ⁡                                          [                                                                                                    (                                                          K                              -                                                              Re                                ⁡                                                                  (                                  r                                  )                                                                                                                      )                                                    2                                                -                                                                              (                                                                                          -                                K                                                            -                                                              Re                                ⁡                                                                  (                                  r                                  )                                                                                                                      )                                                    2                                                                    ]                                                                                                                                                                                                ⁢                                  =                                                            2                      ⁢                      K                      ⁢                                                                                          ⁢                                              Re                        ⁡                                                  (                          r                          )                                                                                                            σ                      2                                                                      ⁢                                                                                                                                                            LLR                  2                                =                                  -                                                            1                                              2                        ⁢                                                  σ                          2                                                                                      ⁡                                          [                                                                                                    (                                                          K                              -                                                              Im                                ⁡                                                                  (                                  r                                  )                                                                                                                      )                                                    2                                                -                                                                              (                                                                                          -                                K                                                            -                                                              Im                                ⁡                                                                  (                                  r                                  )                                                                                                                      )                                                    2                                                                    ]                                                                                                                                                                =                                                            2                      ⁢                      K                      ⁢                                                                                          ⁢                                              Im                        ⁡                                                  (                          r                          )                                                                                                            σ                      2                                                                      ⁢                                                                                                                          (        3        )            
Similarly, when 16 quadrature amplitude modulation (16QAM) is used as a modulation scheme, four bits mapped to one symbol are also independently mapped to the I and Q components. Therefore, an LLR for each bit may be determined from the minimum distance in a one-dimensional space. In 16QAM, however, there are two constellation points having a bit value of “0” and two constellation points having a bit value of “1” in a one-dimensional coordinate system. Therefore, depending on the region where the received symbol r is located, the constellation points which give the minimum distances d0,min and d1,min are different.
Specifically, for example, as illustrated in FIG. 20, for the first bit in a 16QAM constellation, the coordinates of constellation points having a bit value of “0” are K and 3K, and the coordinates of constellation points having a bit value of “1” are −K and −3K. Therefore, a combination of constellation points closest to the received symbol r depends on which of regions 1-1, 1-2 and 1-3 the received symbol r is located. When the received symbol r is included in the region 1-1, of the two constellation points having a bit value of “0”, the one at the coordinate K is closest to the received symbol r; and of the two constellation points having a bit value of “1”, the one at the coordinate −3K is closest to the received symbol. That is, a combination of the constellation points at the coordinates K and −3K gives the minimum distances d0,min and d1,min. Similarly, when the received symbol r is included in the region 1-2, a combination of the constellation points at the coordinates K and −K gives the minimum distances d0,min and d1,min. Also, when the received symbol r is included in the region 1-3, a combination of the constellation points at the coordinates 3K and −K gives the minimum distances d0,min and d1,min.
As described above, depending on the region to which the received symbol r belongs, the constellation points that give the minimum distances are different. Therefore, a log likelihood ratio LLRi for the first bit in 16QAM may be determined for each region from equation (4) below by using the I component (i.e., the real part Re(r)) of the received symbol r:
                              LLR          1                =                  {                                                                                                                4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                          K                                                }                                                                                    σ                      2                                                        ,                                                            Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        2                                            ⁢                      K                                                                                                                                                                                      2                      ⁢                      K                      ⁢                                                                                          ⁢                                              Re                        ⁡                                                  (                          r                          )                                                                                                            σ                      2                                                        ,                                                                                    -                        2                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          2                      ⁢                      K                                                                                                                                                                                      4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                -                          K                                                }                                                                                    σ                      2                                                        ,                                                            2                      ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                                                                                                                    (        4        )            
Since the second bit in 16QAM is mapped to the Q component of the received symbol r, a log likelihood ratio LLR2 may be determined for each region from equation (5) below by using the Q component (i.e., the imaginary part Im(r)) of the received symbol r:
                              LLR          2                =                  {                                                                                                                4                      ⁢                                                                                          ⁢                      K                      ⁢                                              {                                                                              Im                            ⁡                                                          (                              r                              )                                                                                +                          K                                                }                                                                                    σ                      2                                                        ,                                                            Im                      ⁡                                              (                        r                        )                                                              <                                                                  -                        2                                            ⁢                                                                                          ⁢                      K                                                                                                                                                                                      2                      ⁢                                                                                          ⁢                                                                        K                          ⁢                          Im                                                (                        r                        )                                                                                    σ                      2                                                        ,                                                                                    -                        2                                            ⁢                                                                                          ⁢                      K                                        ≤                                          Im                      ⁡                                              (                        r                        )                                                              <                                          2                      ⁢                      K                                                                                                                                                                                      4                      ⁢                                                                                          ⁢                      K                      ⁢                                              {                                                                              Im                            ⁡                                                          (                              r                              )                                                                                -                          K                                                }                                                                                    σ                      2                                                        ,                                                            2                      ⁢                                                                                          ⁢                      K                                        ≤                                          Im                      ⁡                                              (                        r                        )                                                                                                                                                    (        5        )            
On the other hand, as illustrated in FIG. 21, for the third bit in the 16QAM constellation, the coordinates of constellation points having a bit value of “0” are −K and K, and the coordinates of constellation points having a bit value of “1” are −3K and 3K. Therefore, a combination of constellation points closest to the received symbol r depends on which of regions 3-1 and 3-2 the received symbol is located. When the received symbol r is included in the region 3-1, a combination of the constellation points at the coordinates −K and −3K gives the minimum distances. When the received symbol r is included in the region 3-2, a combination of the constellation points at the coordinates K and 3K gives the minimum distances.
Therefore, in 16QAM, a log likelihood ratio LLR3 for the third bit may be determined from equation (6) below, and a log likelihood ratio LLR4 for the fourth bit mapped to the Q component may be determined from equation (7) below:
                              LLR          3                =                  {                                                                                                                2                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            Re                      ⁡                                              (                        r                        )                                                              <                    0                                                                                                                                            -                                                                  2                        ⁢                                                                                                  ⁢                        K                        ⁢                                                  {                                                                                    Re                              (                              r                              )                                                        -                                                          2                              ⁢                                                                                                                          ⁢                              K                                                                                }                                                                                            σ                        2                                                                              ,                                      0                    ≤                                          Re                      ⁡                                              (                        r                        )                                                                                                                                                    (        6        )                                          LLR          4                =                  {                                                                                                                2                      ⁢                                                                                          ⁢                      K                      ⁢                                              {                                                                              Im                            ⁡                                                          (                              r                              )                                                                                +                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            Im                      ⁡                                              (                        r                        )                                                              <                    0                                                                                                                                            -                                                                  2                        ⁢                                                                                                  ⁢                        K                        ⁢                                                  {                                                                                    Im                              ⁡                                                              (                                r                                )                                                                                      -                                                          2                              ⁢                                                                                                                          ⁢                              K                                                                                }                                                                                            σ                        2                                                                              ,                                      0                    ≤                                          Im                      ⁡                                              (                        r                        )                                                                                                                                                    (        7        )            
When 64QAM is used as a modulation scheme, an LLR for each bit may be determined for each region to which the received symbol r belongs. Log likelihood ratios LLR1, LLR3, and LLR5 for the first, third, and fifth bits, respectively, may be determined by equations (8) to (10) below:
                              LLR          1                =                  {                                                                                                                8                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      3                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        6                                            ⁢                      K                                                                                                                                                                                      6                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                                                    -                        6                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        4                                            ⁢                      K                                                                                                                                                                                      4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                          K                                                }                                                                                    σ                      2                                                        ,                                                                                    -                        4                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        2                                            ⁢                      K                                                                                                                                                                                      2                      ⁢                                                                        K                          ⁢                          Re                                                ⁡                                                  (                          r                          )                                                                                                            σ                      2                                                        ,                                                                                    -                        2                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          2                      ⁢                      K                                                                                                                                                                                      4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                -                          K                                                }                                                                                    σ                      2                                                        ,                                                            2                      ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          4                      ⁢                      K                                                                                                                                                                                      6                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                -                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            4                      ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          6                      ⁢                      K                                                                                                                                                                                      8                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                -                                                      3                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            6                      ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                                                                                                                    (        8        )                                          LLR          3                =                  {                                                                                                                4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      5                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        6                                            ⁢                      K                                                                                                                                                                                      2                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      4                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                                                    -                        6                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        2                                            ⁢                      K                                                                                                                                                                                      4                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      3                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                                                    -                        2                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                    0                                                                                                                                                                  4                      ⁢                      K                      ⁢                                              {                                                                              -                                                          Re                              ⁡                                                              (                                r                                )                                                                                                              +                                                      3                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                      0                    ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          2                      ⁢                      K                                                                                                                                                                                      2                      ⁢                      K                      ⁢                                              {                                                                              -                                                          Re                              ⁡                                                              (                                r                                )                                                                                                              +                                                      4                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            2                      ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          6                      ⁢                      K                                                                                                                                                                                      4                      ⁢                      K                      ⁢                                              {                                                                              -                                                          Re                              ⁡                                                              (                                r                                )                                                                                                              +                                                      5                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            6                      ⁢                      K                                        <                                          Re                      ⁡                                              (                        r                        )                                                                                                                                                    (        9        )                                          LLR          5                =                  {                                                                                                                2                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                +                                                      6                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                            Re                      ⁡                                              (                        r                        )                                                              <                                                                  -                        4                                            ⁢                      K                                                                                                                                                                                      2                      ⁢                      K                      ⁢                                              {                                                                              -                                                          Re                              ⁡                                                              (                                r                                )                                                                                                              -                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                                                    -                        4                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                    0                                                                                                                                                                  2                      ⁢                      K                      ⁢                                              {                                                                              Re                            ⁡                                                          (                              r                              )                                                                                -                                                      2                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                      0                    ≤                                          Re                      ⁡                                              (                        r                        )                                                              <                                          4                      ⁢                      K                                                                                                                                                                                      2                      ⁢                      K                      ⁢                                              {                                                                              -                                                          Re                              ⁡                                                              (                                r                                )                                                                                                              +                                                      6                            ⁢                            K                                                                          }                                                                                    σ                      2                                                        ,                                                                                    -                        4                                            ⁢                      K                                        ≤                                          Re                      ⁡                                              (                        r                        )                                                                                                                                                    (        10        )            
Thus, in each modulation scheme, by determining the region to which the received symbol r belongs, an LLR for each bit may be calculated depending on the region. The calculated LLR for each bit is used as soft decision information to perform error correction decoding, for example, turbo decoding. Examples of the related art are disclosed in Japanese Laid-open Patent Publication No. 2009-513087 and Japanese Laid-open Patent Publication No. 2004-104188.
The LLR calculation method described above involves a region determination for each received symbol. This increases the number of determination steps and may cause processing delays. In particular, in high-speed communication, where a large number of received symbols are processed per unit time, it is more likely that larger processing delays may occur.
Specifically, for example, to calculate the LLR for the first bit in 16QAM, a determination is made for each received symbol r as to which of the regions 1-1 to 1-3 is the one to which the received symbol r belongs, and then an operation is performed in accordance with the determination. Also, for example, for the first bit in 64QAM, the LLR may not be calculated without determining, for each received symbol r, which of seven regions is the one to which the received symbol r belongs. Therefore, when the transmission speed increases, the determination processing may not keep up with the speed of receiving symbols and processing delays may occur.
In recent years, Software Defined Radio (SDR) in which signal processing is implemented by software has been widespread. Since execution of the above-described LLR calculations involves many comparison instructions and branch instructions for region determinations, an improvement in processing speed is limited. Specifically, for example, an algorithm for calculating the LLR for the first bit in 64QAM involves sequential comparisons as illustrated in FIG. 22. Compiling this algorithm generates many comparison instructions and branch instructions. To process comparison and branch instructions, some processors require cycles as many as the number of cycles required for processing Arithmetic Logic Unit (ALU) instructions for four arithmetic operations. This leads to increased processing time and may result in processing delays in the SDR.
The SDR allows parallel execution of instructions or operations. However, since the algorithm described above involves sequential comparisons, it may be difficult to improve efficiency through parallel processing. That is, since it may be necessary to sequentially determine whether the received symbol r belongs to each region, it is difficult to fully exploit the performance of architectures, such as Very Long Instruction Word (VLIW) and Single Instruction Multiple Data (SIMD), which allow parallel execution of instructions or operations.